% !TEX encoding = UTF-8 Unicode
\chapter{Separabilidad por círculos entre polígonos convexos}

\section{Nuestro problema}

En esta capítulo plantearemos una variante del problema de transmisión de mensajes utilizando antenas inalámbricas. 

Sean $X, Y$ dos conjuntos de puntos en el plano con $n,m$ puntos respectivamente que representan dos grupos de espías, el primero de aliados y el segundo de enemigos.
Sea $\mathcal A$ una antena inalámbrica con la cual queremos enviar un mensaje en una sola transmisión a todos los espías aliados, 
pero sin que éste sea interceptado por los enemigos.
La potencia de la antena $\mathcal A$ define un radio de transmisión $r$ alrededor del punto de emisión, tal que todo espía a distancia a lo más $r$ de $\mathcal A$ en el momento de la transmisión recibirá el mensaje.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/cap3/CircularSeparability.pdf}
\caption{\small Separabilidad por círculos entre conjuntos de puntos.}
\label{F_CircularSeparability}
\end{center}
\end{figure}

Nuestro objetivo será encontrar la ubicación y potencia óptimas para la antena $\mathcal A$, de modo que transmita el mensaje a todos los espías en $X$, usando la menor potencia posible, y de manera que ningún espía en $Y$ reciba el mensaje. 
Este problema puede verse entonces como un problema de seguridad en el que los mensajes no deben ser interceptados por el enemigo.



Note que la solución al problema, en caso de existir, se puede representar geométricamente a través de el círculo $C$ de radio mínimo que contiene a todo punto de $X$, pero que no contiene a ningún punto de $Y$; ver Figura~\ref{F_CircularSeparability}. 
Dicho de otra forma, podemos referirnos a $C$ como un círculo que separa a los conjuntos de puntos $X$ y $Y$. Note que $C$ divide al plano en dos regiones, el interior del círculo y el exterior del mismo, de manera que $X$ y $Y$ deberán pertenecer a distintas regiones.

El problema de separabilidad por círculos entre conjuntos de puntos ha sido bien estudiado y es un problema clásico en la Geometría Computacional. 
La solución óptima para conjuntos discretos fue presentada por Kosaraju, Megiddo y O'Rourke, quienes propusieron un algoritmo óptimo de tiempo lineal, para encontrar el círculo de radio mínimo que separe a dos conjuntos finitos de puntos cualesquiera~\cite{ComputingCircularSeparability}. 
Este resultado fue extendido en el misma artículo para encontrar el círculo separador de radio mínimo entre dos polígonos simples.

En este trabajo nos interesará la siguiente variante del problema de separación por círculos.
Sean $P,Q$ dos polígonos convexos con $n,m$ vértices respectivamente. 
Imaginemos que $P$ representa un conjunto de torretas situadas en el perímetro de defensa de una ciudad, y $Q$ representa un vehículo enemigo en las inmediaciones de la ciudad.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.85\textwidth]{img/cap3/CircularPolygonSeparability.pdf}
\caption{\small Separabilidad por círculos entre polígonos convexos.}
\label{F_CircularPolygonSeparability}
\end{center}
\end{figure}

Buscaremos entonces colocar nuestra antena en la posición óptima y asignarle la menor potencia posible, 
de manera que toda torreta en el perímetro de defensa reciba los mensajes de la antena, pero del tal forma que en ningún momento el vehículo enemigo $Q$ pueda interceptar algún mensaje.
En este caso la posición óptima de la antena, junto con su potencia, se pueden representar por el círculo de radio mínimo que contiene a $P$ y tal que su interior no intersecta al polígono $Q$; ver Figura~\ref{F_CircularPolygonSeparability}. 
Note que en nuestro problema el vehículo representado por el polígono $Q$ no está fijo, sino que tiene la capacidad de cambiar de posición en las inmediaciones de la ciudad;
sin embargo el conjunto $P$ está fijo, puesto que las torretas no cambian de posición.
Nuestro objetivo será encontrar la posición óptima de la antena en relación a la posición de $Q$ sin importar si éste cambia de posición.

Para facilitar la notación, diremos que $P$ y $Q$ son separables por círculos si existe un círculo separador $C$, tal que su disco cerrado contiene a $P$, y el interior de $C$ no intersecta al polígono $Q$.
En este capítulo formalizamos este problema de separabilidad por círculos de la siguiente manera:
Sea $P$ un polígono convexo con $n$ vértices, buscaremos preprocesar al polígono $P$ para obtener una estructura de datos que soporte consultas de la siguiente forma: 
Dado un polígono convexo $Q$ como la lista de sus $m$ vértices, encontrar el círculo separador de radio mínimo de manera eficiente.

Propondremos un algoritmo que realizará un preprocesado de tiempo lineal sobre los vértices de $P$, lo que nos permitirá encontrar el círculo separador de radio mínimo en tiempo $O(\log n \log m)$ dado cualquier polígono convexo $Q$.

%%%%%%%%%%%%%%%%%
\section{Círculos separadores}
Sean $P,Q$ dos polígonos convexos, cada uno representado por una lista ordenada de vértices (de acuerdo a su posición sobre el cierre convexo de $P$ y $Q$ respectivamente).
Para facilitar la explicación, supongamos que los vértices de $P$ y $Q$ están en posición general y supongamos también que no hay cuatro puntos cocirculares en los vértices de $P$.

\begin{defi}
Diremos que un círculo separa a $P$ de $Q$, si su disco cerrado contiene a $P$ y su interior no intersecta a $Q$. Llamaremos separador, a cualquier círculo que separe a $P$ de $Q$.
\end{defi}

Si pensamos a $P$ como su conjunto de vértices, entonces podemos retomar las definiciones de capítulos anteriores para conjuntos de puntos.
En particular $\mathcal{V}(P)$ denotará al diagrama de Voronoi del punto más lejano de los vértices de $P$, así como
un $P$-círculo será aquel que contiene a todos los vértices de $P$.

Recordemos que $C_P$ denota al $P$-círculo de radio mínimo y $c_P$ a su centro.
Es claro que si $Q$ y $C_P$ tienen interiores ajenos, entonces $C_P$ es un círculo que separa trivialmente a $P$ de $Q$.
Es claro también que si los interiores de $P$ y $Q$ no son ajenos, entonces no existe un círculo separador, por ende supondremos de aquí en adelante que $d(P,Q)>0$.

Note que todo $P$-círculo contenido en un círculo separador es también un círculo separador. Es por esto que ambos conceptos guardan una estrecha relación y 
por ende retomaremos muchas propiedades de los $P$-círculos vistas en capítulos anteriores.

\begin{prop}
El círculo separador de radio mínimo es único.
\end{prop}
\begin{proof}
Procedamos por contradicción y supongamos que existen $C,C'$ dos círculos separadores de radio mínimo con centros $c,c'$ respectivamente; recordemos que en particular $C,C'$ son también $P$-círculos.
Sea $x$ un punto en el intervalo abierto $(c,c')$, por la Proposición~\ref{CirculosEnSegmento} sabemos que $C(x)$ es un $P$-círculo contenido en $C\cup C'$ y por ende $C(x)$ es también un círculo separador.
Más aún, $\rho(x) < \rho(c) = \rho(c')$ por lo que $C(x)$ es un círculo separador de radio menor que $C,C'$ lo cual es una contradicción; concluimos entonces nuestro resultado.

\end{proof}

Gracias a la proposición anterior podemos utilizar la siguiente notación.

\begin{defi}
Sea $c$ el centro del círculo separador de radio mínimo.
\end{defi}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.75\textwidth]{img/cap3/centroEnV(P).pdf}
\caption{\small En esta figura se observa la prueba de la Observación~\ref{centroEnV(P)}.}
\label{F_centroEnV(P)}
\end{center}
\end{figure}

La observación siguiente nos permitirá acotar la búsqueda por $c$, 
a un conjunto de puntos del que conocemos muchas de sus propiedades.


\begin{obs}\label{centroEnV(P)}
El punto $c$ yace sobre una arista de $\mathcal{V}(P)$.
\end{obs}
\begin{proof}
Procedamos por contradicción y supongamos que $c$ está en el interior de $R(p)$ para algún vértice $p$ de $P$. 
Sea $\ell$ la línea recta que pasa por $p$ y $c$;
note que por la Observación \ref{Corta en un solo punto a R(p)}, $\ell$ corta a la frontera de $R(p)$ en un sólo punto. 
Sea entonces $s$ el punto de intersección de la frontera de $R(p)$ y $\ell$, 
es claro que $\rho(s)< \rho(c)$; ver Figura~\ref{F_centroEnV(P)}. 
Además $C(s)$ es un círculo separador pues está contenido en $C(c)$, lo cual es una contradicción pues $C(c)$ es el círculo separador de radio mínimo. 
Concluimos entonces que $c$ pertenece a una arista de $\mathcal{V}(P)$. 
\end{proof}


Presentamos a continuación una serie de propiedades de los círculos separadores que nos permitirán determinar más adelante la posición de $c$.

\begin{prop}\label{AncestroComun}
Sea $p$ un vértice de $P$ y sean $x,y$ dos puntos sobre la frontera de $R(p)$, tales que $C(x),C(y)$ son círculos separadores.
Si $z$ es el primer ancestro común tanto de $x$ como de $y$ en el árbol $\mathcal{V}(P)$ enraizado en $c_P$, entonces $C(z)$ es un círculo separador y $\rho(z)\leq \min\{\rho(x), \rho(y)\}$.
\end{prop}
\begin{proof}
Supongamos que $y\notin \mathcal T_x, x\notin \mathcal T_y$, de lo contrario el resultado se obtiene trivialmente.
Note entonces que las trayectorias que unen a $x$ y $y$ con $z$ tienen interiores ajenos.

Sea $\ell_{z,p}$ la línea recta que pasa por $z$ y $p$; es claro que esta recta deja a $x$ y $y$ en semiplanos distintos. 
Sea $z'$ la intersección de $\ell_{z,p}$ con $[x,y]$; por la Observación~\ref{CirculosEnSegmento} sabemos que $C(z')\subseteq C(x)\cup C(y)$. 
Como $z',z,p$ son colineales, entonces $C(z)\subseteq C(z')$ y por ende $\rho(z)<\rho(z')$; ver Figura \ref{F_AncestroComun}. 
Finalmente, por transitividad de la contención obtenemos que $C(z)\subset C(x)\cup C(y)$, lo cual implica que $C(z)$ es un círculo separador. 
Además, al ser $z$ un ancestro de $x,y$, por el Teorema~\ref{monotonoia rho} concluimos que $\rho(z) < \min\{\rho(x), \rho(y)\}$.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.7\textwidth]{img/cap3/AncestroComun.pdf}
\caption{\small En esta figura se observa la prueba de la Proposición~\ref{AncestroComun}.}
\label{F_AncestroComun}
\end{center}
\end{figure}

\pagebreak
El resultado anterior se generaliza de la siguiente manera.

\begin{lma}\label{AncestroSeparadorGral}
Sean $x,y$ dos puntos sobre $\mathcal{V}(P)$, tales que $C(x)$ y $C(y)$ son círculos separadores.
Si $z$ es el primer ancestro común tanto de $x$ como de $y$ en el árbol enraizado $\mathcal{V}(P)$, entonces $C(z)$ es un círculo separador y $\rho(z)\leq \min\{\rho(x), \rho(y)\}$.
\end{lma}
\begin{proof}
Procedamos por contradicción y supongamos que $C(z)$ no es un círculo separador. 
Sea $w_x$ un punto sobre $\mathcal T_x$ tal que 
$$\rho(w_x) = \min\{\rho(w)\ |\ w\in \mathcal T_{x}\text{ y }C(w)\text{ es un círculo separador}\},$$ 
es claro entonces que $w_x\neq z$. 
Consideremos las intersecciones del segmento cerrado $[w_x,y]$ con $\mathcal{V}(P)$ y supongamos que los puntos de intersección son $w_x = x_0,x_1, \ldots,x_k=y$ en ese orden.
Sea $z'$ es el primer ancestro común de $w_x$ y $x_1$.
Como $w_x$ y $x_1$ pertenecen a la misma región de Voronoi, usando la Proposición~\ref{AncestroComun}, concluimos que $C(z')$ es un círculo separador de radio menor que $C(w_x)$.
Note además que $z'\in \mathcal T_x$ por ser ancestro de $w_x$, lo cual es una contradicción con la definición de $w_x$; concluimos entonces nuestro resultado.
\end{proof}

El siguiente resultado nos permitirá determinar la ubicación de $c$, a partir de la ubicación del centro de un círculo separador arbitrario.

\begin{tma}\label{c en T_s}
Sea $s$ un punto sobre $\mathcal{V}(P)$. Si $C(s)$ es un círculo separador,
entonces $c$ pertence a $\mathcal T_s$.
\end{tma}
\begin{proof}
Sea $w$ un punto sobre una arista de $\mathcal T_s$, tal que 
$$\rho(w) = \min\{\rho(z)\ |\ z\in \mathcal T_{s}\text{ y }C(z)\text{ es un círculo separador}\}.$$
Procedamos por contradicción y supongamos que $c$ no es un punto sobre $\mathcal T_s$, por lo tanto $w\neq c$. Por Lema~\ref{AncestroSeparadorGral}, si $z$ es el primer ancestro común tanto de $c$ como de $w$, entonces $C(z)$ es un círculo separador y $\rho(z)\leq \rho(c)$.
Además, como $c\notin \mathcal T_w\subseteq \mathcal T_s$, entonces la desigualdad es estricta, lo cual es una contradicción que viene de suponer que $w\neq c$; concluimos entonces nuestro resultado.
\end{proof}

El teorema anterior nos permite encontrar a $c$ sobre cualquier trayectoria que una a $c_P$ con el centro de un círculo separador arbitrario.
Por ende nuestro espacio de búsqueda se reduce considerablemente.
Además, recordemos que en el capítulo anterior definimos una estructura de datos que nos permite hacer búsquedas binarias sobre las trayectorias en el árbol $\mathcal{V}(P)$.

Finalmente mostraremos el siguiente resultado que nos será útil en la búsqueda del punto $c$.

\begin{obs}\label{obs:CcTangentToQ}
El $P$-círculo $C(c)$ es tangente al polígono $Q$ en un único punto $q_c$.
\end{obs}
\begin{proof}
Procedamos por contracción y supongamos que $C(c)$ no intersecta al conjunto $Q$, por ende $d(c, Q) > \rho(c)$.
Es claro entonces que por continuidad, existe un punto $x$ a distancia $\varepsilon$ de $c$ sobre $\mathcal T_c$, tal que se sigue cumpliendo que $d(x,Q) > \rho(c)$ y por Teorema~\ref{monotonoia rho} podemos concluir que $\rho(x) < \rho(c)$ lo cual es una contradicción a la minimalidad de $\rho(c)$.
\end{proof}

%%%%%%%%%%%%%%%%%
\section{El algoritmo}
En esta sección presentamos un algoritmo para encontrar a $c$, utilizando la estructura de datos sobre $\mathcal{V}(P)$ presentada en el capítulo anterior. 
Nuestro algoritmo construye primeramente un círculo separador con centro $s_0$, tal que $s_0$ yace sobre una arista de $\mathcal{V}(P)$. Paso seguido, el algoritmo busca por $c$ sobre la trayectoria $\mathcal T_{s_0}$ usando una búsqueda binaria. A continuación describimos el algoritmo a detalle.

Inicialmente revisamos si $C_P$ es o no un círculo separador,  de serlo $C_P$ es el círculo separador de radio mínimo, ejecutar dicha revisión requiere de tiempo $O(\log m)$ al calcular la distancia de $c_P$ a $Q$.
Supondremos de aquí en adelante que $C_P$ no es un círculo separador, por lo tanto el círculo separador de radio mínimo es tangente al polígono $Q$ y procedemos a encontrarlo como sigue.

Calculamos dos puntos $p_0,q_0$ sobre los polígonos convexos $P,Q$ respectivamente, tales que $d(p_0,q_0) = d(P,Q)$.
Dichos puntos se pueden encontrar en tiempo $O(\log n + \log m)$ utilizando el algoritmo propuesto por Edelsbrunner en~\cite{ComputingExtremeDistancesBetweenConvexPolygons}.
Usando la bisectriz del segmento $[p_0,q_0]$, podemos construir una línea recta $L$ que separe a los cierres convexos de $P$ y de $Q$.

Sea $p_L$ el vértice de $P$ más cercano a $L$ y supongamos que no hay otro vértice en $P$ a la misma distancia. De lo contrario rotamos ligeramente a $L$ manteniendo separados a $P$ y $Q$.

Sea $L_\perp$ la recta perpendicular a $L$ que pasa por $p_L$ y sea $s_0$ la intersección de $L_\perp$ con la frontera de $R(p_L)$; 
dicha intersección es única por la Observación~\ref{Corta en un solo punto a R(p)} y se puede calcular en tiempo $O(\log n)$, 
pues es la intersección de un polígono convexo con una línea recta.
Note que $d(s_0, p_L)$ define el radio de $C(s_0)$, por lo tanto $C(s_0)$ es un círculo separador; ver Figura~\ref{F_ConstruccionS_0}.
Note también que por construcción $s_0$ yace sobre una arista de $\mathcal{V}(P)$.
Es claro entonces que podemos calcular a $s_0$ en tiempo $O(\log n + \log m)$.

\begin{figure}[htbp]
\begin{center}
\includegraphics[angle=0, width=.6\textwidth]{img/cap3/ConstruccionS_0.pdf}
\caption{\small La construcción del punto $s_0$.}
\label{F_ConstruccionS_0}
\end{center}
\end{figure}

Supongamos que $s_0$ yace sobre la arista $xy$ de $\mathcal{V}(P)$, y sea 
$$\mathcal T_x = (c_P= u_0, u_1, \ldots, u_{\lambda-1} = y, u_ \lambda = x).$$ 
Por el Teorema~\ref{c en T_s} sabemos que $c$ pertenece a una arista de $\mathcal T_x$.
Usando la estructura de datos propuesta en el capítulo anterior llevamos a cabo la siguiente búsqueda binaria por $c$ sobre los vértices de $\mathcal T_x$.

\begin{alg}\label{Alg busqueda c}
Algoritmo para encontrar a $c$ sobre la trayectoria $\mathcal T_{x}$.
\end{alg}
 \begin{enumerate}
 	\item\ Sea $u = u_\lambda$ el nodo de partida y sea $i = 1$.
	\item\ Sea $v$ el vértice al que punta el $i$-ésimo apuntador de $B_u$.
	\item\ Calculamos $d(v,Q)$ en tiempo logarítmico~\cite{ComputingExtremeDistancesBetweenConvexPolygons} y en tiempo constante calculamos el valor de $\rho(v)$.
	\item\ Si $u$ y $v$ son vértices consecutivos en $\mathcal T_{x}$, entonces terminamos y regresamos la arista $uv$.
	\item\ Si $d(v,Q) = \rho(v)$, entonces $c = v$ y terminamos.
	\item\ Si $d(v,Q) < \rho(v)$, entonces $i = i+1$ y regresamos al paso 2.
	\item\ Si $d(v,Q) > \rho(v)$, entonces $u=v$, $i=1$ y regresamos al paso 2.
\end{enumerate}

El algoritmo anterior concluye y despliega al nodo $c$ si éste es un vértice de $\mathcal T_x$. 
Sin embargo si éste es un punto interior de un segmento, lo cual supondremos de aquí en adelante, entonces el algoritmo despliega dos nodos consecutivos $u,v$ de $T_x$ tales que $c\in [u,v]$. 
Visto de otra forma, tenemos que $\rho(u) < d(u,Q)$ y $\rho(v) > d(v,Q)$, es decir que $C(u)$ es un círculo separador y $C(v)$ ya no lo es; ver Figura~\ref{F_SegmentoS}.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.7\textwidth]{img/cap3/SegmentoS.pdf}
\caption{El segmento $S$ sobre el cual se encuentra $c$.} 
\label{F_SegmentoS}
\end{center}
\end{figure}

\pagebreak
Acotar nuestra búsqueda a este segmento requiere entonces de tiempo $O(\log n \log m)$; 
esto último ya que el Algoritmo~\ref{Alg busqueda c} termina en $O(\log n)$ rondas, 
y cada paso requiere de tiempo constante a excepción del paso 3 que se ejecuta en tiempo $O(\log m)$.
En el apartado siguiente describiremos como encontrar a $c$ una vez que el Algoritmo~\ref{Alg busqueda c} encontró un segmento sobre el que yace el centro del círculo separador de radio mínimo. 

%%%%%%%%%%%%%%%%%
\subsection{Precisando la posición de $c$}

Sea $S = [u, v]$ el segmento obtenido por el Algoritmo~\ref{Alg busqueda c}, recordemos que $c\in S$ y supongamos que $S$ está contenido en la bisectriz de los vértices $p_0,p_1$ de $P$.

Diremos que un punto $q$ de la frontera de $Q$ es visible desde un punto $x$ en $S$, si el segmento abierto $(x,q)$ no intersecta a $Q$. 
Sea $Q_S$ el conjunto de puntos de la frontera de $Q$, visibles desde cualquier punto de $S$. 
Gracias a la convexidad de $Q$, $Q_S$ es la intersección de los puntos visibles desde $u$ y los puntos visibles desde $v$, por ende podemos calcularlo en tiempo $O(\log m)$ usando una búsqueda binaria sobre los vértices de $Q$.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.9\textwidth]{img/cap3/RegionQ_S.pdf}
\caption{La construcción del conjunto $Q_S$ y el punto $q_c$.} 
\label{F_ConstruccionQ_S}
\end{center}
\end{figure}

Por la Observación~\ref{obs:CcTangentToQ}, $C(c)$ es un $P$-círculo tangente al polígono $Q$, por ende definimos a $q_{c}$ como el punto de intersección de $C(c)$ con $Q$. 
Es fácil ver que se cumple el siguiente resultado; ver Figura~\ref{F_ConstruccionQ_S}.
\begin{obs}
El punto $q_{c}$ está en $Q_{S}$, es decir que $q_{c}$ es visible desde cualquier punto de $S$.
\end{obs}

Quisiéramos asociar un punto de $S$ a cada punto de $Q_S$, de modo que pudiéramos buscar por $c$ utilizando los vertices de $Q$ que yacen en $Q_S$. Para ello utilizaremos la siguiente definición.
\begin{defi}
Dados tres puntos $x,y,z\in \mathbb{R}^2$, denotamos por $C(xyx)$ al circumcírculo del triángulo $\triangle(xyz)$.
\end{defi}

Note que para cada punto $q$ en $Q_S$, el centro de $C(p_0qp_1)$ yace sobre el bisector de $p_0,p_1$, más aún, note que el radio de $C(p_0qp_1)$ se incrementa cuando movemos a $q$ hacia $q_c$ y decrementa al alejarnos; ver Figura~\ref{fig:TauEsUnimodal}.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.9\textwidth]{img/cap3/tauEsUnimodal.pdf}
\caption{\small La maximalidad de $q_{c}$ bajo la función $\tau$.} 
\label{fig:TauEsUnimodal}
\end{center}
\end{figure}

Formalmente, definimos a $\tau(x)$ como el radio del círculo $C(p_{0}xp_{1})$.
Es fácil ver que $\tau(x)$ define una función unimodal sobre los puntos de $Q_S$, 
si los recorremos en el sentido de las manecillas del reloj sobre la frontera de $Q$.
Note que, si $w\in [u,c]$, entonces $C(w)$ no intersecta a $Q$ ya que $c$ es el primer punto de $S$ tal que $C(c)$ intersecta a $Q$. 
Por ende para cada punto $q\in Q_S$, 
el círculo $C(p_0qp_1)$ tiene su centro sobre en el segmento $[c,v]\subseteq S$.
Afirmamos que $\tau$ alcanza su máximo en $q_c$ ya que $c$ es el centro de $C(p_0q_cp_1)$ y $c$ es máximo local de la función $\rho$ en el segmento $[c,v]$; ver Figura~\ref{fig:TauEsUnimodal}.

Este resultado nos permitirá realizar una búsqueda binaria por $q_c$ en los vértices de $Q$ que pertenezcan a $Q_S$. Note que necesitamos restringir la búsqueda a $Q_S$, ya que $\tau(x)$ no es unimodal sobre todos los puntos de la frontera de $Q$; ver Figura~\ref{fig:NotUnimodalInAllQ}.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.5\textwidth]{img/cap3/NotUnimodalInAllQ.pdf}
\caption{\small{Ya que el círculo $C(u)$ intersecta a $Q$ en más de dos puntos, $\tau(x)$ no es unimodal cuando la definimos sobre toda la frontera de $Q$, sin embargo lo es cuando la definimos sobre $Q_S$.}} 
\label{fig:NotUnimodalInAllQ}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%
\subsection{Algoritmo para encontrar $q_{c}$}

Implementamos el algoritmo para encontrar a $q_{c}$ sobre $Q_{S}$ como sigue. 
Es claro que en tiempo $O(\log m)$ podemos encontrar los extremos de $Q_{S}$, digamos $q_{0}$ y $q_{r}$.
Sea $Q_{S}^{*} = \{q_0, q_1, \ldots, q_{r}\}$ el conjunto de vértices de $Q$ que pertenecen a $Q_{S}$ y supongamos que se encuentran en ese orden sobre la frontera de $Q$.
Procedemos ahora a realizar una búsqueda binaria por $q_{c}$ sobre los puntos de $Q_{S}^{*}$. 

Inicialmente nuestro espacio de búsqueda será todo el conjunto $Q_{S}^{*}$. 
En cada ronda del algoritmo definimos a $q_i$ como el punto medio del intervalo actual de búsqueda.
Calculamos el valor de $\tau(q_i)$ en tiempo constante y tomamos dos puntos a cada lado de $q_i$ sobre la frontera de $Q$ a distancia epsilon.
Revisamos si $q_i$ es o no un máximo local de $\tau$, de serlo terminamos y lo desplegamos. 
De lo contrario, usamos la unimodalidad de $\tau$ y los puntos a distancia epsilon para averiguar si $q_{c}$ está a la izquierda o a la derecha de $q_i$ en $Q^*_S$. 
Una vez determinado lo anterior redefinimos el intervalo de búsqueda y repetimos recursivamente el proceso.
Formalmente describimos el algoritmo como sigue.
\begin{alg}
Algoritmo para encontrar a $q_{c}$.
\end{alg}
 \begin{enumerate}
	\item[1.]\ Definimos inicialmente el intervalo de la búsqueda de modo que $g = 0$ y $h = r$.
	\item[2.]\ Creamos un apuntador al elemento a la mitad de nuestro intervalo actual de búsqueda, es decir $i= \lceil \frac{g+h}{2}\rceil$.
	\item[3.]\ Tomamos puntos a distancia $\varepsilon  >0$ de $q_i$ hacia $q_{i+1}$ y $q_{i-1}$ sobre la frontera de $Q$, formalmente 
	$q_{i}^{+} = q_i + \varepsilon (q_{i+1} - q_i)$ y 
	$q_{i}^{-} = q_i + \varepsilon (q_{i-1} - q_i)$.
	\item[4.]\ Calculamos en tiempo constante los radios de $C(p_0q_ip_1), C(p_0q_i^+p_1)$ y $C(p_0q_i^-p_1)$. 
	\item[5.]\ Si $\tau(q_i) > \max\{\tau(q_i^+), \tau(q_i^-)\}$, entonces $q_i$ es un máximo de la función $\tau$, por lo tanto $q_{c}= q_i$ con lo que termina el algoritmo.
	\item[6.]\ Si $\tau(q_i) < \tau(q_i^+)$, entonces redefinimos el intervalo de búsqueda al asignar $g = i$.
	\item[7.]\ Si $\tau(q_i) < \tau(q_i^-)$, entonces redefinimos el intervalo de búsqueda al asignar $h = i$.
	\item[8.]\ Si $g,h$ son nodos consecutivos, entonces terminar y desplegar el segmento $H=[q_g, q_h]$.
	De lo contrario regresar al paso 2.
\end{enumerate}

Siendo que descartamos la mitad de los puntos en el intervalo de búsqueda en cada ronda, es claro que el algoritmo anterior termina en $O(\log m)$ rondas. Note también que cada una de las rondas se ejecuta en tiempo constante, por lo tanto el algoritmo anterior termina en tiempo $O(\log m)$.
Al finalizar, el algoritmo despliega el valor de $q_{c}$ si es éste era un vértice de $Q$, o un segmento $H=(q_i,q_{i+1})$ de $Q_S$, tal que $q_{c}$ pertenece a $H$.
En el primer caso habremos concluido, pues una vez encontrado $q_{c}$, en tiempo constante podemos determinar la ubicación de $c$ y por ende encontrar al círculo separador de radio mínimo.

En el segundo caso nuestro problema se reduce a encontrar un punto $c\in S$ tal que $d(c,p_0) = d(c,H)$.
Este caso se resuelve mediante un  sistema de dos ecuaciones con dos incógnitas como sigue. 
Supongamos que la ecuación de la recta que contiene a $H$ es $Ax+By+C=0$ y supongamos también que la ecuación de la recta que contiene a $S$ es $A'x+B'y + C' = 0$. 
Por lo tanto, el sistema de ecuaciones siguiente, cuya solución se puede encontrar en tiempo constante, nos permite precisar la posición del punto $q_{c}$.

\begin{equation}
\sqrt{(c[x]-p_{0}[x])^{2}+(c[y]-p_{0}[y])^{2}} = \frac{|Ac[x]+Bc[y]+C|}{\sqrt{A^{2}+B^{2}}}\\ 
\end{equation}

\begin{equation}
A'c[x] + B'c[y] + C' = 0
\end{equation}

En resumen, el algoritmo encargado de la localización de $q_{c}$ se lleva a cabo en tiempo $O(\log m)$. Dándonos así una complejidad total del algoritmo de consulta de $O(\log n \log m)$.








